
#include "ds/list/List.h"
#include "ds/list/LinkList.h"
#include "ds/list/SqList.h"

/**
 * 描述: 合并两个顺序表，并返回新的合并后的顺序表Lc
 * @La: 递增顺序表
 * @Lb: 递增顺序表
 * @Lc: 保存合并后的新的顺序表
 */
void static MergeList(List *La, List *Lb, List *Lc)
{
    int i = 0, j = 0, k = 0;
    int laLength = La->ListLength();
    int lbLength = Lb->ListLength();

    while (i < laLength && j < lbLength) {
        ElemType ea, eb;
        La->GetElem(i, &ea);
        Lb->GetElem(i, &eb);
        if (ea <= eb) {
            Lc->ListInsert(k++, ea);
            i++;
        } else {
            Lc->ListInsert(k++, eb);
            j++;
        }
    }

    // 下面的两个循环，只有一个会被执行
    while (i < laLength) {
        ElemType e;
        La->GetElem(i, &e);
        Lc->ListInsert(k++, e);
        i++;
    }

    while (j < lbLength) {
        ElemType e;
        Lb->GetElem(j, &e);
        Lc->ListInsert(k++, e);
        j++;
    }

}

int main(int argc, char **argv)
{
#if 0
    List *listA = new SqList;
    List *listB = new SqList;
    List *listC = new SqList;
#else
    List *listA = new LinkList;
    List *listB = new LinkList;
    List *listC = new LinkList;
#endif
    listA->InitList();
    listB->InitList();
    listC->InitList();


    /* 插入 1 2 3 4 5 */
    for(int j = 1; j <= 5; j++)
        listA->ListInsert(j-1, j);

    listA->ListTraverse();

    /* 插入 10 11 12 13 15 */
    for(int j = 6; j > 0; j--)
        listB->ListInsert(0, j+10);

    listB->ListTraverse();

    MergeList(listA, listB, listC);

    listC->ListTraverse();

    return 0;
}
